N개의 최소 공배수

Day 단계 2025-05-30

• 최소 공배수를 구하는 방법은 여러 가지가 있으며, 문제에는 최대 공약수를 사용하여 구하는 방법으로 풀이했다.
• 두 수 a와 b의 최소 공배수 = (a X b ) / (a와 b의 최대 공약수)
• a와 b의 최대 공약수 = (a와 b를 나눈 나머지)와 b를 또 다시 반복 연산

class Solution {
    public int solution(int[] arr) {
        int lacm = 0;
        int lcd = 0;
        int m = 0;

		// 배열의 요소에 대해 반복
		// 최초 lcm 계산 때는 배열의 두 요소 사용
		// 이후엔 lcm과 다음 배열 요소의 최소 공배수 구하기
        for(int i = 0; i < arr.length-1; i++) {
            if(i == 0) {
                lcd = getLCD(arr[i], arr[i+1]);
                m = arr[i] * arr[i+1];
                lacm = m / lcd;
            }
            else {
                lcd = getLCD(lacm, arr[i+1]);
                m = lacm * arr[i+1];
                lacm = m / lcd;
            }
        }
        
        return lacm;
    }

	// 최대 공약수 계산
    public int getLCD(int a, int b) {
        if (b == 0) return a;
        return getLCD(b, a%b);
    }
}

• 더 간략한 풀이

// N개의 최소공배수
public class Main {
    public static void main(String[] args){
        int[] arr = {2, 6, 8, 14};
        int result = lcm(arr[0], arr[1]);
        for (int val: arr) {
            result = lcm(result, val);
        }
        System.out.println(result);
    }

	// 최대 공약수
    public static int gcd(int a, int b){
        if (b != 0){
            return gcd(b, a % b);
        }
        return a;
    }

	// 최소 공배수
    public static int lcm(int a , int b){
        return a * b / gcd(a, b);
    }
}